package letcode.oneQuestionPerDay._202004._22;

import letcode.util.TreeNode;

import java.util.*;

/**
 * @Description: 二叉树的右视图
 * @Date: 2020/4/22
 * @Author: 许群星
 */
public class TwoTreeRightLook_b {

    public static void main(String[] args) {
        TreeNode head=new TreeNode(1);
        head.left=new TreeNode(2);
        head.right=new TreeNode(3);
        head.left.right=new TreeNode(5);
        head.right.right=new TreeNode(4);

        System.out.println(rightSideView(head));
    }

    //提供方法      官方题解：BFS
    //层次遍历，只保留最后边节点
    public static List<Integer> rightSideView(TreeNode root) {
        Map<Integer,Integer> rightmostValueAtDepth=new HashMap<>();
        int max_depth=-1;

        Queue<TreeNode> nodeStack=new LinkedList<>();
        Queue<Integer> depthStack=new LinkedList<>();
        nodeStack.add(root);
        depthStack.add(0);

        while (!nodeStack.isEmpty()){
            TreeNode node=nodeStack.remove();
            int depth=depthStack.remove();

            if (node!=null){
                //维护二叉树的最大深度
                max_depth=Math.max(max_depth,depth);

                //不断更新当前层的最右值
                rightmostValueAtDepth.put(depth,node.val);

                nodeStack.add(node.left);
                nodeStack.add(node.right);
                depthStack.add(depth+1);
                depthStack.add(depth+1);
            }
        }

        List<Integer> rightView=new ArrayList<>();
        for (int i = 0; i <= max_depth; i++) {
            rightView.add(rightmostValueAtDepth.get(i));
        }

        return rightView;
    }
}
/*

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
   \
    5           <---
通过次数26,414提交次数41,125
 */